1. Field
The system and method relates to object tracking and, more particularly, to methods and apparatuses for performing object tracking by solving graph problems.
2. Brief Description
Object tracking, also referred to as video tracking, may be defined as tracking one or more objects across a sequence of video images gathered by one or more cameras. A wide variety of practical applications exist for object tracking, some of which include human-computer interaction, security and surveillance, national defense, video communication and compression, augmented reality, traffic control, medical imaging, and video editing. In general, tracking objects is a challenging problem. Difficulties in tracking objects can arise due to abrupt object motion, changing appearance patterns of both the object and the scene, non-rigid or changing object structures, object-to-object and object-to-scene occlusions, and camera motion. Likewise, object tracking may be a time consuming process due to the amount of data that is contained in the gathered images. Higher-level applications are often utilized in connection with object tracking, and some of these applications require a determination of the location and/or the shape of a target object for every image frame. Adding further to the complexity is the possible need to use object recognition techniques for tracking, a challenging problem in its own right.
One aspect of object tracking is to associate a target object that appears in a series of consecutive video frames. To perform this association, sequential image frames are analyzed to generate an output representing movements of a target object between the frames. The association can be especially difficult when the target object, as well as other objects, are moving fast relative to a rate at which the image frames are gathered. Another situation that increases the complexity of the problem is when the tracked object changes orientation over time. For these situations, object tracking systems may employ a motion model which describes how the image of the target might change for different possible motions of the object.
Multiple Hypothesis Tracking (MHT) is one of the earliest useful method for performing object tracking. MHT builds a tree of potential track hypotheses for each candidate target object, thereby providing a systematic solution to data association problems. A likelihood of each track is calculated, and a most likely combination of tracks is selected. MHT is ideally suited to exploiting higher-order information such as long-terra motion and appearance models, since the entire track hypothesis can be considered when computing the likelihood of each track.
In a typical, track-oriented MHT implementation, a tree/forest data structure is utilized. As measurements come in, new leaf nodes are created and incorporated to represent possible track hypotheses. A best global solution in the form of a set of compatible track hypotheses with the best association likelihood is then obtained by solving a linear integer programming problem. The width of the tree can grow exponentially with the number of measurements in such an approach, and thus pruning becomes a crucial part of MHT.